package com.demo.图;

import com.demo.图.model.Graph;
import com.demo.图.model.Vertex;

import java.util.*;

/**
 * @author cl
 */
public class GraphTraverse {

    /** 宽度优先遍历 */
    public static <T> List<Vertex<T>> traverseByWidth(Graph<T> graph) {
        if(Objects.isNull(graph) || graph.vertexMap.isEmpty()) {
            return Collections.emptyList();
        }
        List<Vertex<T>> result = new ArrayList<>();
        Queue<Vertex<T>> traverse = new LinkedList<>();
        // 对应有向图 存在 in 为0 的顶点
        for (Vertex<T> tmp : graph.vertexMap.values()) {
            if (tmp.in == 0) {
                traverse.add(tmp);
            }
        }
        // 无向图了
        if (traverse.size() == 0) {
            traverse.add(graph.vertexMap.values().iterator().next());
        }
        // 存储已经遍历了的
        HashSet<Vertex<T>> alreadyPrint = new HashSet<>();
        while (!traverse.isEmpty()) {
            Vertex<T> c = traverse.poll();
            if (alreadyPrint.contains(c)) {
                continue;
            }
            result.add(c);
            alreadyPrint.add(c);
            traverse.addAll(c.nexts);
        }
        return result;
    }

    /** 深度优先遍历 */
    public static <T> List<Vertex<T>> traverseByHeight(Graph<T> graph) {
        if(Objects.isNull(graph) || graph.vertexMap.isEmpty()) {
            return Collections.emptyList();
        }
        List<Vertex<T>> result = new ArrayList<>();
        Stack<Vertex<T>> stack = new Stack<>();
        // 对应有向图 存在 in 为0 的顶点
        for (Vertex<T> tmp : graph.vertexMap.values()) {
            if (tmp.in == 0) {
                stack.push(tmp);
            }
        }
        // 无向图了
        if (stack.size() == 0) {
            stack.add(graph.vertexMap.values().iterator().next());
        }
        // 存储已经遍历了的
        HashSet<Vertex<T>> alreadyPrint = new HashSet<>();
        while (!stack.isEmpty()) {
            Vertex<T> c = stack.pop();
            if (!alreadyPrint.contains(c)) {
                result.add(c);
                alreadyPrint.add(c);
            }
            Vertex<T> next = null;
            for (Vertex<T> t : c.nexts) {
                if (!alreadyPrint.contains(t)) {
                    next = t;
                    break;
                }
            }
            // 继续一条路走到黑
            if (next != null) {
                stack.push(c);
                stack.push(next);
            }
        }
        return result;
    }
}
